#include<bits/stdc++.h>
using namespace std;

const int MAXN=1000+10;

char str1[MAXN];
char str2[MAXN];

int Fun1(int n,int m){
    int answer;
    if(n==0||m==0){
        answer=0;
    }else{
        if(str1[n]==str2[m]){
            answer=Fun1(n-1,m-1)+1;
        }else{
            answer=max(Fun1(n-1,m),Fun1(n,m-1));
        }
    }
    return answer;
}

int memo[MAXN][MAXN];
int Fun2(int n,int m){
    if(memo[n][m]!=-1){
        return memo[n][m];
    }
    int answer;
    if(n==0||m==0){
        answer=0;
    }else{
        if(str1[n]==str2[m]){
            answer=Fun2(n-1,m-1)+1;
        }else{
            answer=max(Fun2(n-1,m),Fun2(n,m-1));
        }
    }
    memo[n][m]=answer;
    return answer;
}

int dp[MAXN][MAXN];
void Fun3(int n,int m){
    for(int i=0;i<=n;++i){
        for(int j=0;j<=m;++j){
            int answer;
            if(i==0||j==0){
                answer=0;
            }else{
                if(str1[i]==str2[j]){
                    answer=dp[i-1][j-1]+1;
                }else{
                    answer=max(dp[i-1][j],dp[i][j-1]);
                }
            }
            dp[i][j]=answer;
        }
    }
    return;
}

int main(){
    while(scanf("%s%s",str1+1,str2+1)!=EOF){
        int n=strlen(str1+1);
        int m=strlen(str2+1);
        //recursive,O(2^(n+m))
        //int maximum=Fun1(n,m);
        //printf("%d\n",maximum);

        //recursive+memorize,O(n*m)
        /*for(int i=0;i<=n;++i){
            for(int j=0;j<=m;++j){
                memo[i][j]=-1;
            }
        }
        int maximum=Fun2(n,m);
        printf("%d\n",maximum);
        */
        //recurrent，递推求解O(n*m)
        for(int i=0;i<=n;++i){
            for(int j=0;j<=m;++j){
                memo[i][j]=-1;
            }
        }
        Fun3(n,m);
        int maximum=dp[n][m];
        printf("%d\n",maximum);
    }
}
